https://www.nowcoder.com/practice/237ae40ea1e84d8980c1d5666d1c53bc?tpId=230&tqId=2032575&ru=/exam/oj&qru=/ta/dynamic-programming/question-ranking&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196

#include <iostream>
#include<cstring>
using namespace std;

const int N=1010;
int n,V,v[N],w[N],dp[N];

int main()
{
    cin>>n>>V;
    for(int i=1;i<=n;i++)
        cin>>v[i]>>w[i];

    for(int i=1;i<=n;i++)
    {
        for(int j=v[i];j<=V;j++)
        {
            dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
        }
    }
    cout<<dp[V]<<endl;

    memset(dp,0,sizeof(dp));

    for(int i=1;i<=V;i++)
        dp[i]=-0x3f3f3f3f;
    
    for(int i=1;i<=n;i++)
    {
        for(int j=v[i];j<=V;j++)
        {
  
                dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
        }
    }
    cout<<(dp[V]<0?0:dp[V])<<endl;
    return 0;
}